﻿//https://leetcode.cn/problems/minimum-number-of-frogs-croaking/

//我的1：
class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        if (croakOfFrogs[0] != 'c')return -1;
        string croakStr = { "croak" };
        int len = croakStr.size();
        vector<int> hash(croakStr.size(), 0);

        int ret = 0, cur = 0;
        for (int i = 0; i < croakOfFrogs.size(); i++)
        {
            char curChar = croakOfFrogs[i];
            int pos = croakStr.find(curChar);
            hash[pos]++;
            if (pos == 0)
            {
                hash[0]++;
                cur++;
                if (cur > ret)ret = cur;
            }
            else
            {
                hash[pos]++;
                if (hash[pos - 1] < hash[pos]) return -1;
                if (pos == len - 1)cur--;
            }

        }
        for (auto& t : hash) {
            if (t != hash[0])return -1;
        }
        return ret;
    }
};
//答案
class Solution
{
public:
	int minNumberOfFrogs(string croakOfFrogs)
	{
		string t = "croak";
		int n = t.size();
		vector<int> hash(n); // ⽤数组来模拟哈希表
		unordered_map<char, int> index; //[x, x这个字符对应的下标]
		for (int i = 0; i < n; i++)
			index[t[i]] = i;
		for (auto ch : croakOfFrogs)
		{
			if (ch == 'c')
			{
				if (hash[n - 1] != 0) hash[n - 1]--;
				hash[0]++;
			}
			else
			{
				int i = index[ch];
				if (hash[i - 1] == 0) return -1;
				hash[i - 1]--; hash[i]++;
			}
		}
		for (int i = 0; i < n - 1; i++)
			if (hash[i] != 0)
				return -1;
		return hash[n - 1];
	}
};